The ordered dither method and the error diffusion method are widely used to express halftones of photographs or the like in printers, facsimiles and the like that form an image with dots. The ordered dither method is realized by quantizing (binarizing) a pixel of multi-gradation image data based on a corresponding threshold value in a dither matrix. FIG. 86 to FIG. 88 show the ordered dither method.
FIG. 86A is multi-gradation data before being dithered, FIG. 86B is a 4×4 size dither matrix, and FIG. 86C is two gradation data after being dithered.
In the ordered dither method, the multi-gradation data before being dithered (FIG. 86A) is compared with a value (threshold value) of the dither matrix (FIG. 86B). As a result of comparison, when the multi-gradation data before being dithered (FIG. 86A) is larger than a corresponding element value (threshold value) of the dither matrix (FIG. 86B), the dithered data becomes “1”. When the multi-gradation data before being dithered (FIG. 86A) is smaller than the corresponding element value (threshold value) of the dither matrix (FIG. 86B), the dithered data becomes “0”. The two gradation data (FIG. 86C) after being dithered is obtained in such a manner. Since the dither matrix is repeatedly used, the same periodic feature as that of the dither matrix appears in the image created through this method (the dithered binary image in FIG. 86C). Particularly, this feature remarkably appears in images with a large quantity of low frequency component such as photographs. FIG. 87A to FIG. 87C show another example when the ordered dither method is used.
Compression and encoding of the dithered image is performed in many cases by using such a periodic feature of the dithered image. For example, Japanese Patent No. 1379237 discloses a technology of predicting a value of an encoding target pixel by using an encoded pixel apart from the encoding target pixel by a dither period and its peripheral pixels, and by encoding a prediction error. Japanese Patent No. 1807514, Japanese Patent No. 2113692, and Japanese Patent No. 2113693 disclose a technology of sorting in-block pixels in descending order by dither threshold values in a predetermined pixel block (dither matrix) unit and encoding the pixels. According to such technologies, the result of dithering the image with a large quantity of low frequency component has been largely affected by the dither threshold values. Therefore, black pixels and white pixels gather respectively through the sorting, which allows high degree of compression. Japanese Patent Application Laid-Open No. 7-231390 discloses a technology of arithmetic-coding a distance between reconstructed multi-gradation data and dither threshold values as estimated probability. Japanese Patent No. 1402929, Japanese Patent No. 2634793, and Japanese Patent No. 2713298 disclose a technology of collecting pixels with highly estimated probability and pixels with low estimated probability in predetermined pixel block units and encoding the respective pixels, although these patents do not refer to the dithered image. According to such technologies, it is possible to obtain an effect that compression efficiency does not decrease even when estimated probability within an image varies because pixels with high estimated probability are collected.
As a technique of performing processing on a dithered image having such periodicity and creating a simplified image through simplification such as low resolution and removal of a detailed structure, a technology of focusing on threshold values of a dither matrix has been known. For example, in Japanese Patent Application Laid-Open No. 9-135352, threshold values at positions to be thinned are previously dispersed for low resolution, and a density jump is minimized to achieve a higher degree of image quality. As explained above, a simplified image obtained by preserving only main information in an original image and removing unnecessary fine information has a smaller amount of codes when being compressed as compared to the original image, thus suppressing the costs at the time of its storage and reducing the time for its transfer.
The dither matrix has plural types such as a concentration type and a dispersion type. FIG. 88A to FIG. 88D show the concentration type and dispersion type dither matrices. FIG. 88A is multi-gradation data before being dithered, FIG. 88B is a 4×4 size concentration type dither matrix, FIG. 88C is a 4×4 size dispersion type dither matrix, and FIG. 88D is two gradation data after being dithered. In the examples of FIG. 88B and FIG. 88C, both of the dither sizes (i.e., the size of the dither matrix) are based on 4×4, but the dither size may be any size of 4×4 to 64×64, or may be any whose main size and auxiliary size may be different. The example of FIG. 88D shows the two gradation data obtained by dithering the multi-gradation data of FIG. 88A based on the dispersion type dither matrix of FIG. 88C.
For example, Japanese Patent Application Laid-Open No. 7-99581 discloses an example of image area separation for a binarized and reduced, a continuous element area is extracted from the reduced image, and this extracted area is integrated with the previously classified data to determine a type of image. In this processing example, since binary processing is executed in an image processor, which type of dither matrices (dither type and size) has been used for dithering is previously known.
The error diffusion method is a method of quantizing (binarizing) a pixel of multi-gradation image data using a predetermined threshold value, multiplying an error occurring at the time of its quantization by respective factors of an error diffusion matrix, and distributing the obtained values to adjacent pixels to be quantized. The image processed through this error diffusion method (error-diffused image) is excellent in resolution as compared to the dithered image, and has no periodicity appearing between dots unlike the dithered image.
As one of the conventional technologies on compression and encoding of an error-diffused image, there is Japanese Patent Application Laid-Open No. 7-79352, which discloses a technology of predicting density of a remarked area, selecting one of predetermined sorting rules based on this prediction, and concentrating pixels randomly dispersed by applying the rule to improve a compression rate.
There is a variety of threshold values for a dither matrix and factors of an error diffusion matrix. In a document with a plurality of objects such as text, graphics, or photograph, dither threshold values or error diffusion factors may sometimes be different from one another for each object within a page.
The conventional technology for the dithered image, however, is based on the fact that the threshold values for a used dither matrix are already known. Therefore, efficient encoding cannot be expected in any dithered image whose dither threshold values are unknown or dither threshold values vary.